/*
7-199 原根
分数 150
作者 马俊
单位 兰州大学

在数论，特别是整除理论中，原根是一个很重要的概念。

对于给定的正整数 p 和一个正整数 a(1<a<p)，如果 a 与 p 互质，即
gcd(a,p)=1，且使得 a^b≡1(modp) 成立的最小正整数 b 的取值为 φ(p)，则称 a 为模 m
的一个原根。

其中，gcd(a,p) 的含义是 a 与 p
的最大公约数，即二者公共因数中最大的一个；a^b≡1(modp) 的含义是 ab 除以 p
的余数为 1；φ(p) 的含义是 p 的“欧拉函数”，即在所有小于等于 p 的正整数中与 p
互质的数的数目。

现在给定一个正整数 p，请你求出 p 的原根。
输入格式:

一行，一个整数 p(3≤p≤3000)，代表题目中描述的正整数
输出格式:

一行，一个整数 a(1<a<p)，代表 p 的一个原根（如果 p
的原根有多个，则输出最小的一个，如果 p 没有满足条件的原根，则输出 -1）
输入样例1:

3

输出样例1:

2

输入样例2:

5

输出样例2:

2

输入样例3:

8

输出样例3:

-1

样例解释：

对于样例 1：由于 φ(3)=2，满足 a^φ(3)≡1(mod3) 且不超过 3 的正整数 a 只有
1,2；因为 1 不满足条件，因此 3 的原根为 2；

对于样例 2：由于 φ(5)=4，满足 a^φ(5)≡1(mod5) 且不超过 5 的正整数 a 有
1,2,3,4；但是由于满足 4^b≡1(mod5) 的正整数 b 可以为 2(2<φ(5))，故排除 4，因此 5
的最小原根为 2；

对于样例 3：可以证明，不存在任何 1<a<8 能够满足原根的条件。
*/

#include <stdio.h>

// φ(p) 的含义是 p 的“欧拉函数”，即在所有小于等于 p 的正整数中与 p
// 互质的数的数目。
int phi(int p) {
    int result = p;
    for (int i = 2; i * i <= p; i++) {
        if (p % i == 0) {
            while (p % i == 0) {
                p /= i;
            }
            result -= result / i;
        }
    }
    if (p > 1) {
        result -= result / p;
    }
    return result;
}

int main() {
    int p;
    scanf("%d", &p);
    // p = 5;
    int fp = phi(p);
    // 从2开始枚举，然后暴力判断a^φ(p) = 1 (mod P)是否当且当指数为φ(p)的时候成立
    for (int a = 2; a < p; a++) {
        int aa = 1;
        int flag = 1;
        // 暴力判断a^φ(p) = 1 (mod P)是否当且当指数为φ(p)的时候成立
        for (int i = 1; i < fp; i++) {
            aa = aa * a % p;
            // 指数不为φ(p)的时候，模p之后为1，说明不是原根
            if (aa == 1) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            // 指数为φ(p)的时候，模p之后为1，说明是原根
            aa = aa * a % p;
            if (aa == 1) {
                printf("%d", a);
                return 0;
            }
        }
    }
    printf("-1");
    return 0;
}